package com.heima.datastructure.graph;

import java.util.*;
import java.util.function.Consumer;
import java.util.stream.Collectors;

/**
 * <h2>图</h2>
 * <p>此实现是有向图</p>
 *
 * @author 勾新杰
 * @version 1.0
 * @date 2024/10/7 17:28
 */
public class Graph {
    // 邻接表存储图
    private final List<Vertex> vertices; // 顶点集合，因为顶点会隐含边，所以这些顶点的集合足以表示一个图

    private int verticesCount; // 顶点个数

    private int edgesCount; // 边个数

    private static final int UNVISITED = Integer.MAX_VALUE; // 无穷大值，用于表示距离的最大值

    /**
     * 无参构造初始化
     */
    public Graph() {
        this.vertices = new ArrayList<>();
    }

    /**
     * 用于测试
     *
     * @param vertices 顶点集合
     */
    public Graph(List<Vertex> vertices) {
        this.vertices = vertices;
        this.verticesCount = vertices.size();
        for (Vertex vertex : vertices) {
            edgesCount += vertex.edges.size();
        }
    }

    // 一、可变对象 vs 不可变对象：
    //    1、在 Java 中，“可变（mutable）”和“不可变（immutable）”是两个重要的概念，用于描述对象在其生命周期中是否可以被修改。
    //    2、可变对象：
    //      （1）定义：可变对象是指在其创建后，可以修改其状态或内容的对象。对于可变对象，你可以更改其内部数据，而无需创建一个新的对象。
    //      （2）例子：StringBuilder、StringBuffer、集合类(List、Map那些)、自定义的那些类（修改属性）
    //      （3）优点：
    //               性能高：由于不需要每次修改都创建新对象，操作通常更快，特别是在需要频繁修改的情况下
    //               内存使用：由于没有频繁地创建新对象，可以节省内存。
    //      （4）缺点：
    //               线程安全：可变对象在多线程环境中不安全，多个线程同时修改同一个对象可能会导致数据不一致。
    //               易用性：在函数参数中使用可变对象可能导致意外修改原始对象。
    //    3、不可变对象：
    //      （1）定义：不可变对象是指在其创建后，无法更改其状态或内容的对象。对不可变对象的任何修改都会导致创建一个新对象，而不是改变原始对象。
    //      （2）例子：String，Integer, Double, LocalDate等包装类和LocalDate, LocalTime, LocalDateTime等时间日期类
    //      （3）优点：
    //               线程安全：不可变对象是线程安全的，多个线程可以安全地共享同一个对象，而无需额外的同步。
    //               简化设计：由于对象状态不变，避免了许多潜在的错误和复杂性。使得设计更简单，易于理解。
    //               缓存和优化：可以使用缓存策略来优化性能。例如，Java 在内部实现了字符串池来优化字符串对象的创建。
    //      （4）缺点：
    //               性能开销：频繁创建新对象可能会导致性能下降和内存使用增加，尤其是在需要大量修改时。
    //               不可直接修改：如果需要修改不可变对象的某些属性，通常需要创建一个新的对象，并且可能会引入额外的复杂性

    /**
     * 顶点类
     */
    public static class Vertex { // 静态内部类不能访问外部类的实例成员，但是可以访问外部类的静态成员
        String name; // 顶点名称，理应保证唯一性
        List<Edge> edges; // 顶点对应的边，无向图就是所有度，有向图就是所有出度
        boolean visited; // 顶点是否被访问过，用于遍历算法中，默认初始化为false
        int inDegree; // 入度个数，值得注意的是，这个属性图结构并不维护其正确性，只在拓扑排序时会用他，其余情况该属性的值都是0，而且一轮拓扑排序结束后，该属性会重置为0，默认初始化0
        int status; // 顶点状态，用于拓扑排序，默认是0，表示未访问，1表示已访问，2表示已入栈，这个属性也是图本身并不维护其正确性，专门给拓扑排序的DFS实现用，一轮拓扑排序结束后，该属性会重置为0
        int distance; // 记录某一顶点到源点的距离，用于最短路径算法、最小生成树Prim算法，默认为Integer.MAX_VALUE，由迪杰特斯拉算法、贝尔曼福特、Prim算法维护其正确性，意思就是进行一次最短路径算法后这个属性就会变成该次算法源顶点到当前顶点的最短距离
        Vertex prev; // 记录某个顶点到当前顶点的路径中当前顶点的前一个顶点，用于最短路径算法、最小生成树Prim算法，由迪杰特斯拉算法、贝尔曼福特算法、Prim算法维护其正确性，意思就是进行一次最短路径算法后这个属性就会变成该次算法源顶点到当前顶点的最短距离路径中上一个顶点

        public Vertex(String name) {
            this.name = name;
            this.edges = new ArrayList<>();
            this.distance = UNVISITED;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Vertex vertex = (Vertex) o;
            return Objects.equals(name, vertex.name);
        }

        @Override
        public int hashCode() {
            return Objects.hash(name);
        }

        @Override
        public String toString() {
            StringBuilder builder = new StringBuilder();
            builder.append(name);
            edges.forEach(edge -> builder.append(" --").append(edge.weight).append("--> ").append(edge.linked.name));
            return builder.toString();
        }

        public String getName() {
            return name;
        }

        public Vertex getPrev() {
            return prev;
        }
    }

    /**
     * 边类
     */
    public static class Edge { // 在添加边的时候需要指定连接的顶点，所以外界也应该可以访问
        // 为什么只设置一个顶点，是因为推荐采用邻接表来存储图，相对于邻接矩阵更加节省空间，
        // 邻接表是数组结合链表存储图的，当前节点存到数组中某个元素，
        // 当前节点的出度（有向图）连接的另一个节点存储即可
        // 不同的边就依次串到当前节点对应数组元素位置的后面去。
        Vertex linked; // 边连接的顶点
        int weight; // 边权重
        int start; // 边起点的节点的索引，基本操作不维护，用于克鲁斯卡尔算法
        int end; // 边终点的节点的索引，基本操作不维护，用于克鲁斯卡尔算法

        public Edge(Vertex linked) {
            this(linked, 1);
        }

        public Edge(Vertex linked, int weight) {
            this.linked = linked;
            this.weight = weight;
        }

        @Override
        public String toString() {
            return String.valueOf(weight);
        }

        public int getWeight() {
            return weight;
        }
    }

    /**
     * 根据名称查找顶点
     *
     * @param name 顶点名称
     * @return 顶点
     */
    public Vertex findVertex(String name) {
        return vertices.stream().filter(vertex -> vertex.name.equals(name)).findFirst().orElse(null);
    }

    /**
     * 判断是否包含顶点
     *
     * @param name 顶点名称
     * @return 包含返回true，否则返回false
     */
    public boolean containsVertex(String name) {
        return vertices.stream().anyMatch(vertex -> vertex.name.equals(name));
    }

    /**
     * 判断从from到to是否有路径
     *
     * @param from 始顶点名称
     * @param to   终顶点名称
     * @return true表示有路径，false表示无路径
     */
    public boolean hasPath(String from, String to) {
        List<Vertex> vertex = new ArrayList<>();
        // 这里既可以是广度优先搜索，也可以是深度优先搜索
        dfs(from, v -> {
            if (v.name.equals(to)) {
                vertex.add(v);
            }
        });
        // 始顶点与终顶点相同，自己到自己肯定有路径
        if (from.equals(to)) {
            return true;
        }
        // 始顶点与终顶点不相同，遍历结果为空，表示无路径
        return !vertex.isEmpty();
    }

    /**
     * 判断图是否有环
     *
     * @return true表示有环，false表示无环
     */
    public boolean hasCircle() {
        try {
            topologicalSort();
        } catch (IllegalStateException exception) {
            return true;
        }
        return false;
    }

    /**
     * 获取某顶点的邻接顶点集合，在有向图中，邻接顶点集合只包含该顶点的出度对应的另一边节点，而在无向图中就没区别
     *
     * @param name 顶点名称
     * @return 邻接顶点的集合
     * @throws IllegalArgumentException 如果顶点不存在，抛出异常
     */
    public List<Vertex> adjacentVertexes(String name) {
        Vertex vertex = findVertex(name);
        if (vertex == null) {
            throw new IllegalArgumentException("未找到顶点，顶点不存在");
        }
        return vertex.edges.stream().map(edge -> edge.linked).collect(Collectors.toList());
    }

    /**
     * 获取所有顶点
     *
     * @return 所有顶点
     */
    public List<Vertex> vertices() {
        return vertices;
    }

    /**
     * 获取所有边
     *
     * @return 所有边
     */
    public List<Edge> edges() {
        // flatMap将流中的每个元素映射成一个流，将所有流合并成一个新流
        return vertices.stream().flatMap(vertex -> vertex.edges.stream()).collect(Collectors.toList());
    }

    /**
     * 添加顶点
     * <p>应当是单纯的添加节点，如果节点带有边，那么相当于另一个顶点也加上了，所以这里不能用Vertex作为参数</p>
     *
     * @param name 顶点名称
     * @throws IllegalArgumentException 如果节点已存在，抛出异常
     */
    public void addVertex(String name) {
        // 判断是否已存在
        if (vertices.stream().anyMatch(vertex -> vertex.name.equals(name))) {
            throw new IllegalArgumentException("该节点已存在");
        }
        // 创建出要添加的节点
        Vertex vertex = new Vertex(name);
        vertex.edges = new ArrayList<>();
        // 添加
        vertices.add(vertex);
        verticesCount++;
    }

    /**
     * 添加边
     * <p>也应当是单纯的添加边，参数可以是Vertex，但是用String更好一些</p>
     *
     * @param from 边始顶点的名称
     * @param to   边终顶点的名称
     */
    public void addEdge(String from, String to) {
        addEdge(from, to, 1);
    }

    /**
     * 添加带权重的边
     *
     * @param from   边始顶点的名称
     * @param to     边终顶点的名称
     * @param weight 权重
     * @throws IllegalArgumentException 如果边已存在，或者找不到给定的两个顶点，抛出异常
     */
    public void addEdge(String from, String to, int weight) {
        // 找到始顶点和终顶点
        Vertex fromVertex = findVertex(from);
        Vertex toVertex = findVertex(to);
        // 如果至少有一个未找到，那么抛出异常
        if (fromVertex == null || toVertex == null) {
            throw new IllegalArgumentException("未找到始顶点和终顶点");
        }
        // 判断该边是否已经存在，并且权重是否重复，都满足，那么抛出异常
        for (Edge edge : fromVertex.edges) {
            if (edge.linked == toVertex) {
                if (edge.weight != weight) {
                    edge.weight = weight;
                    return;
                }
                throw new IllegalArgumentException("该边已存在");
            }
        }
        // 添加边
        fromVertex.edges.add(new Edge(toVertex, weight));
        edgesCount++;
    }

    /**
     * 删除顶点
     *
     * @param name 顶点名称
     * @throws IllegalArgumentException 如果顶点不存在，抛出异常
     */
    public void removeVertex(String name) {
        // 找到要删除的顶点
        Vertex removed = findVertex(name);
        // 如果未找到，抛出异常
        if (removed == null) {
            throw new IllegalArgumentException("未找到顶点，顶点不存在");
        }
        // 先删除该顶点，等同于删除了该顶点以及该顶点指出的所有边
        vertices.remove(removed);
        verticesCount--;
        edgesCount -= removed.edges.size(); // 删除顶点时也要把删除的边的数量减去
        // 删除指向该顶点的边
        for (Vertex vertex : vertices) {
            // 增强for循环内不能有删除操作，会报错ConcurrentModificationException
            // 具体原因：
            // 大多数 Java 集合类（如 ArrayList、HashSet 等）在内部会维护一个修改计数器（modCount）。这个计数器在集合被修改时（添加或删除元素）会增加。
            // 当使用迭代器（例如增强 for 循环）遍历集合时，Java 会检查这个计数器。如果在遍历过程中集合被修改（除了通过迭代器的 remove 方法外），则会抛出 ConcurrentModificationException。
            // 这样做的目的是在迭代过程中防止数据不一致性
            // for (Edge edge : vertex.edges) {
            //     if (edge.linked == removed){
            //         vertex.edges.remove(edge);
            //         edgesCount--;
            //     }
            // }
            // 解决方案：
            // 1、使用迭代器遍历集合，而不是直接使用增强 for 循环
            // 2、将要删除的元素存储在一个临时集合中，然后在遍历结束后统一删除。
            // 3、使用普通的 for 循环来遍历集合。
            Iterator<Edge> iterator = vertex.edges.iterator();
            while (iterator.hasNext()) {
                Edge edge = iterator.next();
                if (edge.linked == removed) {
                    iterator.remove(); // 安全删除当前迭代到的元素
                    edgesCount--;
                }
            }
        }
    }

    /**
     * 删除边
     *
     * @param from 始顶点名称
     * @param to   终顶点名称
     * @return 删除的边的权重
     * @throws IllegalArgumentException 如果边不存在，抛出异常
     */
    public int removeEdge(String from, String to) {
        // 找到始顶点
        Vertex fromVertex = findVertex(from);
        // 如果未找到，抛出异常
        if (fromVertex == null) {
            throw new IllegalArgumentException("未找到始顶点，边不存在");
        }
        // 找到始顶点对应的边
        Edge find = fromVertex.edges.stream().filter(edge -> edge.linked.name.equals(to)).findFirst().orElse(null);
        // 如果未找到边，抛出异常
        if (find == null) {
            throw new IllegalArgumentException("未找到边，边不存在");
        }
        // 删除边
        fromVertex.edges.remove(find);
        edgesCount--;
        return find.weight;
    }

    /**
     * 顶点个数
     *
     * @return 顶点个数
     */
    public int verticesCount() {
        return verticesCount;
    }

    /**
     * 边个数
     *
     * @return 边个数
     */
    public int edgesCount() {
        return edgesCount;
    }

    /**
     * DFS(Depth First Search)深度优先遍历
     *
     * @param consumer 消费者，接收当前顶点
     */
    public void dfs(Consumer<Vertex> consumer) {
        for (Vertex vertex : vertices) {
            if (!vertex.visited) {
                dfs1(vertex, consumer);
                // dfs2(vertex, consumer);
            }
        }
        // 深度优先遍历结束后，重置所有顶点的访问标记
        for (Vertex vertex : vertices) {
            vertex.visited = false;
        }
    }

    /**
     * 从指定顶点开始，深度优先遍历
     *
     * @param name     顶点名称
     * @param consumer 消费者，接收当前顶点
     */
    public void dfs(String name, Consumer<Vertex> consumer) {
        dfs1(findVertex(name), consumer);
        // dfs2(findVertex(name), consumer);
        for (Vertex vertex : vertices) {
            vertex.visited = false;
        }
    }

    /**
     * 递归实现DFS，从左至右
     *
     * @param vertex   当前顶点
     * @param consumer 消费者，接收当前顶点
     */
    private void dfs1(Vertex vertex, Consumer<Vertex> consumer) {
        consumer.accept(vertex);
        vertex.visited = true; // 接收后再设置已访问
        for (Edge edge : vertex.edges) {
            Vertex next = edge.linked;
            if (!next.visited) {
                dfs1(next, consumer);
            }
        }
    }

    /**
     * 非递归实现DFS，从右至左，值得注意的是非递归的DFS，每一层顺序是从后到前，也就是从链表末尾到开始，原因就是栈的特性
     *
     * @param vertex   当前顶点
     * @param consumer 消费者，接收当前顶点
     */
    private void dfs2(Vertex vertex, Consumer<Vertex> consumer) {
        // 创建栈，用于记录未走的路，栈顶元素为下一个要走的路
        LinkedList<Vertex> stack = new LinkedList<>(); // 用链表实现栈，因为栈会频繁的压入和弹出元素
        // 压入DFS开始顶点
        stack.push(vertex);
        // 循环栈非空
        while (!stack.isEmpty()) {
            // 弹出栈顶元素，走当前路
            Vertex pop = stack.pop();
            consumer.accept(pop);
            pop.visited = true;
            // 遍历当前顶点的所有边，如果未访问过，则压入栈，作为接下来要走的路
            for (Edge edge : pop.edges) {
                // 因为这里是依次从链表（边）头到尾压入栈，所以下一个要走的节点是链表尾部边对应的节点
                Vertex next = edge.linked;
                if (!next.visited) {
                    stack.push(next);
                }
            }
        }
    }

    /**
     * BFS(Breadth First Search)广度优先遍历
     *
     * @param consumer 消费者，接收当前顶点
     */
    public void bfs(Consumer<Vertex> consumer) {
        for (Vertex vertex : vertices) {
            bfs(vertex, consumer);
        }
        // 广度优先遍历结束后，重置所有顶点的访问标记
        for (Vertex vertex : vertices) {
            vertex.visited = false;
        }
    }

    /**
     * 从指定顶点开始，广度优先遍历
     *
     * @param name     顶点名称
     * @param consumer 消费者，接收当前顶点
     */
    public void bfs(String name, Consumer<Vertex> consumer) {
        Vertex vertex = findVertex(name);
        if (vertex == null) {
            return;
        }
        bfs(vertex, consumer);
        // bfs(findVertex(name), consumer);
        for (Vertex v : vertices) {
            v.visited = false;
        }
    }

    /**
     * BFS
     *
     * @param vertex   当前顶点
     * @param consumer 消费者，接收当前顶点
     */
    private void bfs(Vertex vertex, Consumer<Vertex> consumer) {
        // 创建队列
        LinkedList<Vertex> queue = new LinkedList<>();
        // 添加起始顶点，走当前路，并设置已访问，每次元素入队的时候都要设置已访问，不允许相同元素重复入队
        queue.offer(vertex);
        vertex.visited = true;
        while (!queue.isEmpty()) {
            Vertex poll = queue.poll();
            consumer.accept(poll);
            for (Edge edge : poll.edges) {
                Vertex next = edge.linked;
                if (!next.visited) {
                    queue.offer(next);
                    // 这里也需要设置已访问，否则会有相同的元素重复入队
                    next.visited = true;
                }
            }
        }
    }

    /**
     * <strong>拓扑排序是一个用于有向无环图（DAG, Directed Acyclic Graph）的排序方法,它将图中的所有顶点线性排列，同时确保如果存在一条从顶点 A 到顶点 B 的边，则在排序结果中 A 出现在 B 之前。拓扑排序在很多应用中非常重要，如任务调度、编译顺序等。拓扑排序中越往后的达成条件越多</strong>
     *
     * @return 拓扑排序结果
     */
    public List<Vertex> topologicalSort() {
        // return topologicalSort1();
        return topologicalSort2();
    }

    /**
     * 用入度法实现拓扑排序 Kahn's Algorithm
     *
     * @return 拓扑排序结果
     */
    private List<Vertex> topologicalSort1() {
        // 创建队列、结果集合
        LinkedList<Vertex> queue = new LinkedList<>();
        List<Vertex> result = new ArrayList<>();
        // 统计各个顶点的入度
        // vertices.forEach(vertex -> vertex.edges.forEach(edge -> edge.linked.inDegree++));
        for (Vertex vertex : vertices) {
            for (Edge edge : vertex.edges) {
                edge.linked.inDegree++;
            }
        }
        // 统计那些顶点的入度为0，并且将这些顶点加入队列中
        // vertices.stream().filter(vertex -> vertex.inDegree == 0).forEach(queue::offer);
        for (Vertex vertex : vertices) {
            if (vertex.inDegree == 0) {
                queue.offer(vertex);
            }
        }
        // 依次取出队列中的顶点放入结果集合中，并遍历每个顶点的邻接顶点，将这些邻接顶点的入度减1
        while (!queue.isEmpty()) {
            Vertex poll = queue.poll();
            result.add(poll);
            for (Edge edge : poll.edges) {
                edge.linked.inDegree--;
                // 如果有邻接顶点的入度减为0了，那么将这些顶点加入队列中
                if (edge.linked.inDegree == 0) {
                    queue.offer(edge.linked);
                }
            }
        }
        // 重复上述步骤，直到队列为空，此时结果集合即为拓扑排序的结果，而且如果无环，上述结束后每个顶点的inDegree会置为0
        // 到这里为止，如果说图中存在环，假设环的入口为e，那么当遍历到e的时候，e的inDegree不可能减为0，也就永远不可能加入队列中，那么环内的所有顶点都不可能被加入到队列中，也就不会加入到结果集合中返回，有环的时候拓扑排序就会缺斤少两
        // 出现环的位置，不仅环内的所有元素都不会被遍历到，而且圈后面的（箭头指向的方向），也可以说出口顶点指出的一堆，都不会被遍历到
        if (result.size() != verticesCount) {
            throw new IllegalStateException("存在环");
        }
        return result;
    }

    /**
     * 用深度优先遍历实现拓扑排序 DFS
     * <p>为什么可以用DFS求解？因为DFS本质就是遍历当前顶点尽可能深入的每一个分支，查找分支的过程可以维护节点之间的依赖性，越深入，需要达成条件越多，就应该排在靠后，越浅，需要达成条件越少，就应该排在前面</p>
     *
     * @return 拓扑排序结果
     */
    private List<Vertex> topologicalSort2() {
        LinkedList<Vertex> stack = new LinkedList<>();
        dfsForTopologicalSort(stack);
        // 栈顶元素就是拓扑排序的第一个元素，因为用的链表实现的栈
        return stack;
    }

    /**
     * 针对拓扑排序的深度优先遍历，在深度优先遍历结束后，将所有顶点的状态重置为0，遍历过程中，将所有顶点由深到浅排列，也就是拓扑排序的结果
     *
     * @param stack 栈，用于存放拓扑排序的结果
     */
    private void dfsForTopologicalSort(LinkedList<Vertex> stack) {
        vertices.forEach(vertex -> {
            if (vertex.status == 0) {
                // 一个顶点拓扑排序结束后，对应子图的顶点都会被置为2
                dfsForTopologicalSort(vertex, stack);
            }
        });
        // 重置所有顶点的状态
        vertices.forEach(vertex -> vertex.status = 0);
    }

    /**
     * 递归深度优先遍历，在遍历过程中，将所有顶点由深到浅排列，也就是拓扑排序的结果
     *
     * @param vertex 当前顶点
     * @param stack  存放拓扑排序的结果
     */
    private void dfsForTopologicalSort(Vertex vertex, LinkedList<Vertex> stack) {
        // 当前顶点已访问
        vertex.status = 1;
        // 准备访问当前顶点的邻接顶点对应的子图
        for (Edge edge : vertex.edges) {
            Vertex next = edge.linked;
            // 如果邻接顶点不存在，那么边也不会存在，那么会直接跳过
            // 如果邻接顶点未访问，则递归深度优先遍历
            if (next.status == 0) {
                dfsForTopologicalSort(next, stack);
            }
            // 如果邻接顶点已访问，而不是已入栈，则存在环，意思就是准备访问的下一个顶点是之前已经访问过的一个顶点，此时说明存在环
            else if (next.status == 1) {
                throw new IllegalStateException("存在环");
            }
            // 邻接顶点已入栈，此时说明已经访问过，而且已经加入到排序结果中了，这个顶点不需要再访问了
            else {
                continue;
            }
        }
        // 当前顶点入栈，入栈时机要是在归的时候，因为深度越深，达成条件越多，所以应当将那些入度为0的排在最前面，在这里就应当是栈顶
        stack.push(vertex);
        vertex.status = 2;
    }

    /**
     * 迪杰特斯拉算法，不能处理负边（边权重为负数）
     *
     * @param from 起始顶点
     * @return 返回起始顶点到其他顶点的最短距离
     */
    public Map<Vertex, Integer> dijkstra(String from) {
        // 将每个顶点的距离重置为无穷大,将所有顶点的前一个前一个置为null
        vertices.forEach(v -> {
            v.distance = UNVISITED;
            v.prev = null;
        });
        // 创建一个结果集合，用于存放最终的结果
        Map<Vertex, Integer> result = new HashMap<>();
        // 找到起始顶点
        Vertex vertex = findVertex(from);
        if (vertex == null) {
            throw new IllegalArgumentException("起始顶点不存在");
        }
        // 用迪杰特斯拉算法进行计算每个顶点到vertex顶点的最短距离
        dijkstra(vertex, result);
        vertices.forEach(v -> v.visited = false);
        // 返回结果集合
        return result;
    }

    /**
     * 迪杰特斯拉算法
     *
     * @param from   起始顶点
     * @param result 结果集合
     */
    private void dijkstra(Vertex from, Map<Vertex, Integer> result) {
        // 创建一个集合来存储未访问的节点
        PriorityQueue<Vertex> unvisitedQueue = new PriorityQueue<>(Comparator.comparingInt(v -> v.distance)); // 默认是小顶堆
        vertices.forEach(unvisitedQueue::offer);
        // 将起始顶点的距离设置为0
        from.distance = 0;
        // 循环遍历未访问集合，直到集合为空
        while (!unvisitedQueue.isEmpty()) {
            // 遍历未访问集合中的顶点，找出距离最小的顶点
            Vertex minVertex = unvisitedQueue.peek();
            // 对该顶点的在未访问集合中的邻接顶点进行遍历，更新其距离
            if (minVertex.visited) { // 因为后面可能会重复的往优先级队列中加入同一个对象的引用，只是排的位置不一致，最后一次加入的（最后一次更新距离）会排在前面
                unvisitedQueue.poll(); // 遇到已访问过的，就出队删除
                continue;
            }
            updateVertexDistance(minVertex, unvisitedQueue);
            // 移除当前的距离最小顶点
            unvisitedQueue.poll();
            minVertex.visited = true;
            // 将已访问的顶点的距离放入结果集合中
            result.put(minVertex, minVertex.distance);
        }
    }

    /**
     * 根据当前未访问集合中距离最小顶点更新未访问集合中顶点的距离
     *
     * @param minVertex      距离最小的顶点
     * @param unvisitedQueue 未访问集合
     */
    private void updateVertexDistance(Vertex minVertex, PriorityQueue<Vertex> unvisitedQueue) {
        // 遍历当前顶点的邻接顶点
        for (Edge edge : minVertex.edges) {
            Vertex next = edge.linked;
            // 如果邻接顶点未访问，则更新其距离
            if (!next.visited) {
                int newDistance = minVertex.distance + edge.weight; // edge.weight 最小都是1
                if (minVertex.distance != UNVISITED && newDistance < next.distance) {
                    next.distance = newDistance;
                    next.prev = minVertex;
                    // 更新优先级队列
                    unvisitedQueue.offer(next);
                }
            }
        }
    }

    /**
     * 贝尔曼-福德算法，可以处理负边（边权重为负数）
     *
     * @param from 起始顶点
     * @return 返回起始顶点到其他顶点的最短距离
     */
    public Map<Vertex, Integer> bellmanFord(String from) {
        // 创建返回结果集合
        Map<Vertex, Integer> result = new HashMap<>();
        // 找到起始顶点
        Vertex vertex = findVertex(from);
        // 如果起始顶点不存在，抛出异常
        if (vertex == null) {
            throw new IllegalArgumentException("起始顶点不存在");
        }
        // 将每个顶点的距离重置为无穷大,将所有顶点的前一个前一个置为null
        vertices.forEach(v -> {
            v.distance = UNVISITED;
            v.prev = null;
        });
        // 将起始顶点的距离设置为0
        vertex.distance = 0;
        // 循环遍历所有顶点，共n-1次，因为n个顶点个数的图进行一次贝尔曼福德算法，会对这个图的所有边遍历n - 1次
        for (int i = 0; i < vertices.size() - 1; i++) {
            // 遍历所有顶点的出度，也就是遍历所有边
            for (Vertex v : vertices) {
                v.edges.forEach(
                        // 遍历每个顶点的每条边
                        edge -> {
                            // 获取当前边的邻接顶点
                            Vertex next = edge.linked;
                            int newDistance = v.distance + edge.weight;
                            // 如果当前顶点到邻接顶点的距离小于邻接顶点的距离，则更新邻接顶点的距离和前一个顶点
                            if (v.distance != UNVISITED && newDistance < next.distance) {
                                next.distance = newDistance;
                                next.prev = v;
                            }
                        }
                );
            }
        }
        // 再来一次循环，如果会存在负环的话，每个顶点的最小距离还会继续被更新，检测到要更新，则抛出异常
        vertices.forEach(v -> v.edges.forEach(
                edge -> {
                    Vertex next = edge.linked;
                    int newDistance = v.distance + edge.weight;
                    if (v.distance != UNVISITED && newDistance < next.distance) {
                        throw new IllegalStateException("存在负环");
                    }
                }
        ));
        // 将每个顶点的距离放入结果集合中
        vertices.forEach(v -> result.put(v, v.distance));
        // 返回结果集合
        return result;
    }

    /**
     * Floyd-Warshall多源最短路径算法，上述的dijkstra算法和bellman-ford算法都是单源最短路径算法。而且floyd-warshall算法可以处理负边，可是还是处理不了负环
     *
     * @return 所有顶点到其他顶点的最短距离的集合
     */
    public void floydWarshall() {
        /*
           假设有这样一个图(邻接表)：
           v1 -- -2 --> v3
           v2 --  4 --> v1 --  3 --> v3
           v3 --  2 --> v4
           v4 -- -1 --> v2

           则求出v1~v4分别到其他顶点的最短路径算法过程：（floydWarshall）

           k = 0  这一步负责初始化二维数组
                v1  v2  v3  v4
            v1   0   ∞  -2   ∞
            v2   4   0   3   ∞
            v3   ∞   ∞   0   2
            v4   ∞  -1   ∞   0

           k = 1  这一步表示所有顶点借助v1到其它顶点是否存在更短的路径，存在则更新
                v1  v2  v3  v4
            v1   0   ∞  -2   ∞
            v2   4   0   2   ∞
            v3   ∞   ∞   0   2
            v4   ∞  -1   ∞   0

           k = 2  这一步表示所有顶点借助v2到其它顶点是否存在更短的路径，存在则更新
                v1  v2  v3  v4
            v1   0   ∞  -2   ∞
            v2   4   0   2   ∞
            v3   ∞   ∞   0   2
            v4   3  -1   1   0

           k = 3  这一步表示所有顶点借助v3到其它顶点是否存在更短的路径，存在则更新
                v1  v2  v3  v4
            v1   0   ∞  -2   0
            v2   4   0   2   4
            v3   ∞   ∞   0   2
            v4   3  -1   1   0

           k = 4  这一步表示所有顶点借助v4到其它顶点是否存在更短的路径，存在则更新
                v1  v2  v3  v4
            v1   0  -1  -2   0
            v2   4   0   2   4
            v3   5   1   0   2
            v4   3  -1   1   0

           则得出结果：
                    v1：到v1的最短距离：0，到v2的最短距离：-1，到v3的最短距离：-2，到v4的最短距离：0
                    v2：到v1的最短距离：4，到v2的最短距离： 0，到v3的最短距离： 2，到v4的最短距离：4
                    v3：到v1的最短距离：5，到v2的最短距离： 1，到v3的最短距离： 0，到v4的最短距离：2
                    v4：到v1的最短距离：3，到v2的最短距离：-1，到v3的最短距离： 1，到v4的最短距离：0
         */

        // 图为空
        if (verticesCount == 0) {
            throw new IllegalArgumentException("图为空");
        }
        // 创建距离和路径二维数组
        int[][] distances = new int[verticesCount][verticesCount];
        Vertex[][] previos = new Vertex[verticesCount][verticesCount]; // previous[i][j]表示从i到j的最短路径的j的上一个节点
        // 对二维数组进行赋初值
        for (int i = 0; i < verticesCount; i++) {
            // 获取第i个节点
            Vertex source = vertices.get(i);
            // 将第i个节点的所有邻接顶点以及对应边的距离赋值给map
            Map<Vertex, Integer> map = source.edges.stream().collect(Collectors.toMap(edge -> edge.linked, edge -> edge.weight));
            for (int j = 0; j < verticesCount; j++) {
                // 获取第j个节点
                Vertex destination = vertices.get(j);
                // 如果两个顶点相同，则跳过
                if (source == destination) {
                    // 自己到自己前一个顶点设置为null
                    continue;
                }
                // 如果两个顶点不相等，则将两个顶点之间的距离赋值给二维数组，或者两个顶点之间没有边，则设置距离为无穷大
                Integer distance = map.getOrDefault(destination, UNVISITED);
                // 设置当前位置的初值
                distances[i][j] = distance;
                // 设置当前位置的前一个顶点
                previos[i][j] = distance == UNVISITED ? null : source;
            }
        }
        System.out.println(formatDistanceMatrix(distances));
        System.out.println(formatPreviousMatrix(previos));
        // 每轮每个顶点借助一个顶点到其他位置的最距离是否能更新最短距离，一共要借助verticesCount顶点个数
        for (int k = 0; k < verticesCount; k++) {
            // 当前轮的顶点
            for (int i = 0; i < verticesCount; i++) {
                // 当前轮的顶点到其它的那些的顶点
                for (int j = 0; j < verticesCount; j++) {
                    // 如果说借助顶点是本轮源顶点 或者 借助顶点是本轮目的顶点 或者 源顶点到借助顶点距离无穷大 或者 借助顶点到目的顶点距离无穷大，则跳过
                    // 当i == k || k == j时矩阵对应位置的值不会改变，哪怕i == j的时候也不会改变，只有当k与i、j不等时
                    if (i == k || k == j || distances[i][k] == UNVISITED || distances[k][j] == UNVISITED) {
                        continue;
                    }
                    // 计算新的距离
                    int newDistance = distances[i][k] + distances[k][j];
                    // 如果新的距离小于旧的距离，则更新
                    if (newDistance < distances[i][j]) {
                        // 如果自己到自己的最小距离为负数，那么抛出异常
                        if (newDistance < 0 && i == j) {
                            throw new IllegalStateException("存在负环");
                        }
                        distances[i][j] = newDistance;
                        previos[i][j] = previos[k][j];
                    }
                }
            }
            System.out.println(formatDistanceMatrix(distances));
            System.out.println(formatPreviousMatrix(previos));
        }
        /* 负环情况：
           假设有这样一个图(邻接表)：存在负环
           v1 --  2 --> v2
           v2 -- -4 --> v3
           v3 --  1 --> v1 --  1 -->v4

           k = 0  这一步负责初始化二维数组
                v1  v2  v3  v4
            v1   0   2   ∞   ∞
            v2   ∞   0  -4   ∞
            v3   1   ∞   0   1
            v4   ∞   ∞   ∞   0

           k = 1  这一步表示所有顶点借助v1到其它顶点是否存在更短的路径，存在则更新
                v1  v2  v3  v4
            v1   0   2   ∞   ∞
            v2   ∞   0  -4   ∞
            v3   1   3   0   1
            v4   ∞   ∞   ∞   0

           k = 2  这一步表示所有顶点借助v2到其它顶点是否存在更短的路径，存在则更新
                v1  v2  v3  v4
            v1   0   2  -2   ∞
            v2   ∞   0  -4   ∞
            v3   1   3  -4   1
            v4   ∞   ∞   ∞   0

           // 到这里看出问题了，v3 到 v3的最短距离变成了负数，那么如果再绕着环走两圈，最短距离会更小

           k = 3  这一步表示所有顶点借助v3到其它顶点是否存在更短的路径，存在则更新
                v1  v2  v3  v4
            v1  -1   1  -2  -1
            v2  -3  -1  -4  -3
            v3   1   3  -4   1
            v4   ∞   ∞   ∞   0

           // 从这里也看得出，所有顶点的最短距离都会跟着不断缩小
         */
        // 输出路径
        printPaths(previos);
    }

    /**
     * 距离二维数组转成字符串
     *
     * @param distances 二维数组
     * @return 字符串
     */
    private String formatDistanceMatrix(int[][] distances) {
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < verticesCount; i++) {
            builder.append("[ ");
            for (int j = 0; j < verticesCount; j++) {
                if (distances[i][j] == UNVISITED) {
                    builder.append(" ").append("∞");
                } else if (distances[i][j] < 0) {
                    builder.append(distances[i][j]);
                } else {
                    builder.append(" ").append(distances[i][j]);
                }
                if (j == verticesCount - 1) {
                    builder.append(" ");
                } else {
                    builder.append(", ");
                }
            }
            builder.append(" ]\r\n");
        }
        return builder.toString();
    }

    /**
     * 上一个节点二维数组转成字符串
     *
     * @param previos 二维数组
     * @return 字符串
     */
    private String formatPreviousMatrix(Vertex[][] previos) {
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < verticesCount; i++) {
            builder.append("[  ");
            for (int j = 0; j < verticesCount; j++) {
                if (previos[i][j] == null) {
                    builder.append(previos[i][j]);
                } else {
                    builder.append(previos[i][j].name).append("   ");
                }
                if (j == verticesCount - 1) {
                    builder.append(" ");
                } else {
                    builder.append(", ");
                }
            }
            builder.append(" ]\r\n");
        }
        return builder.toString();
    }

    /**
     * 打印所有最短路径
     *
     * @param previos 上一个节点二维数组
     */
    private void printPaths(Vertex[][] previos) {
        LinkedList<Vertex> stack = new LinkedList<>();
        for (int i = 0; i < verticesCount; i++) {
            Vertex from = vertices.get(i);
            for (int j = 0; j < verticesCount; j++) {
                Vertex to = vertices.get(j);
                System.out.print("[" + from.name + "到" + to.name + "]: ");
                int toIndex = j;
                while (to != null && to != from) {
                    stack.push(to);
                    to = previos[i][toIndex];
                    toIndex = indexOf(to);
                }
                stack.push(from);
                List<String> list = stack.stream().map(v -> v.name).collect(Collectors.toList());
                String join = String.join(" -> ", list);
                System.out.println(join);
                System.out.println();
                stack.clear();
            }
        }
    }

    /**
     * 获取顶点在顶点列表中的索引
     *
     * @param vertex 顶点
     * @return 索引
     */
    private int indexOf(Vertex vertex) {
        for (int i = 0; i < vertices.size(); i++) {
            if (vertices.get(i) == vertex) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 最小生成树Prim算法，以顶点为核心，类似于迪杰斯特拉算法
     *
     * @return 最小生成树，键为顶点，值为该顶点的prev顶点
     */
    public Map<Vertex, Vertex> prim() {
        // 顶点为空，返回null
        if (verticesCount == 0) {
            throw new IllegalArgumentException("顶点为空");
        }
        // 先对prev、distance属性置初始化，值为null、∞
        vertices.forEach(vertex -> {
            vertex.prev = null;
            vertex.distance = UNVISITED;
        });
        // 选择第一个节点作为起始节点，distance置为0
        vertices.get(0).distance = 0;
        // 创建结果集合
        HashMap<Vertex, Vertex> result = new HashMap<>();
        // 进行核心算法
        prim(result);
        // 重置所有顶点已访问状态为false
        vertices.forEach(v -> v.visited = false);
        // 返回结果
        return result;
    }

    /**
     * prim核心算法
     *
     * @param result 结果集合封装的是每个顶点的prev顶点以及之间的距离
     */
    private void prim(Map<Vertex, Vertex> result) {
        // 选取顶点中距离最小的顶点进行处理，这里用优先级队列
        PriorityQueue<Vertex> queue = new PriorityQueue<>(verticesCount, Comparator.comparingInt(v -> v.distance));
        vertices.forEach(queue::offer);
        while (!queue.isEmpty()) {
            Vertex poll = queue.poll();
            // 如果已访问过，则跳过
            if (poll.visited) {
                continue;
            }
            // 是否需要更新此顶点的邻接顶点
            for (Edge edge : poll.edges) {
                // 获取当前边的权重
                int newDistance = edge.weight;
                // 获取当前边的邻接顶点
                Vertex next = edge.linked;
                // 判断是否需要更新, 如果邻接顶点未访问过，且新距离小于旧距离，则更新
                if (!next.visited && newDistance < next.distance) {
                    next.distance = newDistance;
                    next.prev = poll;
                    // 更新后，重新加入优先级队列，优先级高会放在没更新之前的next顶点之前
                    queue.offer(next);
                }
            }
            // 处理完，置为已访问
            poll.visited = true;
            // 添加到结果集合
            result.put(poll, poll.prev);
        }
    }

    /**
     * 最小生成树Kruskal算法（克鲁斯卡尔），基于并查集
     *
     * @return 结果集合
     */
    @SuppressWarnings("all")
    public void kruskal() {
        // 遍历所有边给start和end赋值
        vertices.forEach(v -> v.edges.forEach(e -> {
            e.start = indexOf(v);
            e.end = indexOf(e.linked);
        }));
        // 将所有边存入优先级队列中
        PriorityQueue<Edge> queue = new PriorityQueue<>(edgesCount, Comparator.comparingInt(e -> e.weight));
        vertices.forEach(v -> queue.addAll(v.edges));
        // 创建一个并查集
        DisjointSet set = new DisjointSet(verticesCount);
        // 创建存放边集合
        ArrayList<Edge> list = new ArrayList<>(verticesCount - 1);
        // 循环verticesCount - 1次，n个顶点最小生成树边个数：n - 1
        while (list.size() < verticesCount - 1) {
            // 每次取出最小的边，判断边对应的两个顶点是否联通
            Edge poll = queue.poll();
            int root1 = set.find(poll.start);
            int root2 = set.find(poll.end);
            // 如果联通（同一棵树），则跳过
            if (root1 == root2) {
                continue;
            }
            // 否则添加到结果集合中，并合并两个顶点，联通两个集合，也就是合并成一棵树
            list.add(poll);
            set.union(root1, root2);
        }
        // 打印结果
        list.forEach(edge -> System.out.println(vertices.get(edge.start).name + " -- " + edge.weight + " --> " + vertices.get(edge.end).name));
        // 重置所有边顶点索引
        vertices.forEach(v -> v.edges.forEach(e -> {
            e.start = 0;
            e.end = 0;
        }));
    }

    /**
     * 并查集(不相交集合)
     */
    public static class DisjointSet {
        // 索引对应不同的顶点
        // 现在想象这个数组中对应的所有顶点分成若干个大集合（数组相当于森林，分成的若干的集合就是森林里的一棵棵树）
        // 然后每个大集合都设置一个根顶点来代表这个大集合，而一个元素的父顶点可能还有父顶点，相当于嵌套的集合，可以想象一棵树，父顶点就是子树根节点，根顶点就是整棵树的根节点
        // 索引处的元素值则表示该顶点所在局部集合（子树）的父顶点索引
        // 所以如果两个顶点的根顶点相等，则说明这两个顶点属于同一个大集合（整棵树）说明连通，否则不相等，则属于不同的大集合（两颗不同的树）不连通
        int[] parent; // 取parent就是表示该索引处的顶点所在局部集合中的父顶点
        int[] size; // 顶点所在集合的元素个数

        /**
         * 初始化并查集
         *
         * @param size 顶点个数
         */
        public DisjointSet(int size) {
            parent = new int[size];
            this.size = new int[size];
            // 每个顶点只与自己构成只有一个元素的大集合
            for (int i = 0; i < size; i++) {
                parent[i] = i;
                this.size[i] = 1;
            }
        }

        /**
         * 找到索引x对应的顶点所在大集合的根顶点，每个大集合就是一棵树，根顶点就是代表
         *
         * @param x 顶点索引
         * @return 根顶点索引
         */
        public int find(int x) {
            // 先看自己是不是所处集合的根顶点
            if (x == parent[x]) {
                return x;
            }
            // 如果不是，则递归找当前局部集合（子树）的父顶点是不是大集合（整棵树）的根顶点
            // 优化：路径压缩，就是将当前顶点直接指向根顶点，这样下次再找的时候，不用再递归找了，不仅如此，递归中间的那些顶点也会被指向根顶点，这样下次再找的时候，也不用再递归找了
            return parent[x] = find(parent[x]);
        }

        /**
         * union是让两个大集合合并，x是大集合1的根顶点，y是大集合2的根顶点
         *
         * @param root1 大集合1的根顶点
         * @param root2 大集合2的根顶点
         */
        public void union(int root1, int root2) {
            // 为了减少查找根顶点时的递归深度，应当把规模较小的树接到规模较大的树下，递归深度得到缓解，union by size
            if (size[root1] < size[root2]){
                int temp = root1;
                root1 = root2;
                root2 = temp;
            }
            // 将大集合2的根顶点指向大集合1的根顶点，也就是将root2对应的大集合接到root1对应的大集合下作为root1的局部集合，也就是将树2变成树1的一部分
            parent[root2] = root1;
            // 更新较大集合1的元素个数
            size[root1] += size[root2];
        }
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        for (Vertex vertex : vertices) {
            builder.append(vertex.toString()).append("\r\n");
        }
        return builder.toString();
    }
}
